package leetcode;

import java.util.LinkedList;

//将树中结点的next指向其右边的结点，若没有右结点，则指向null
public class PopulateNextLinkNode {

	public class TreeLinkNode {
		int val;
		TreeLinkNode left, right, next;
		TreeLinkNode(int x) {
			val = x;
		}
	}

	//with O(1) space
	//but the OJ time is 580ms
	
	public void connect2(TreeLinkNode root) {
		if(root == null){
			return;
		}
		TreeLinkNode pre = root;
		TreeLinkNode cur = null;
		while (pre.left != null) {
			cur = pre;
			while (cur != null) {
				cur.left.next = cur.right;
				if (cur.next != null)
					cur.right.next = cur.next.left;
				cur = cur.next;
			}
			pre = pre.left;
		}
	}
	
	//time is 440ms for first problem
	//运行时间：736ms
	//占用内存：2969k for the second problem
	public void connect(TreeLinkNode root) {
		if(root == null){
			return;
		}
		int toBeConnect = 1;  //还有多少个需要连接
		int nextCount = 0;
		
		LinkedList<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();
		queue.add(root);
		while(!queue.isEmpty()){
			TreeLinkNode temp = queue.peek();
			if(temp.left != null){
				queue.add(temp.left);
				nextCount++;
			}
			if(temp.right != null){
				queue.add(temp.right);
				nextCount++;
			}
			queue.remove();
			if(toBeConnect <= 1){
				toBeConnect = nextCount;
				nextCount = 0;
				temp.next = null;
			}else {
				temp.next = queue.getFirst();
				toBeConnect --;
			}
		}
	}
}
